package pl.pw.gis.gc_sa.algo;

import pl.pw.gis.gc_sa.data.Graph;
import pl.pw.gis.gc_sa.data.Vertex;
import pl.pw.gis.gc_sa.data.VertexChange;

/**
 * Klasa implementujaca algorytm losowo przeszukujacy przestrzen rozwiazan,
 * uzywany w celach porownawczych
 * 
 * @author Maciek
 * 
 */
public class RandomSearch extends GcSolver {

    /** Aktualna lista kolorow */
    protected int[] mCurrentSolution;

    /** Konstruktor przyjmuje jako parametr niepokolorowany graf */
    public RandomSearch(Graph graph) {
        super(graph);
    }

    public RandomSearch(Graph graph, int noChangeMax, int noIter) {
        super(graph);
        mNoChangeIter = noChangeMax;
        mNoIterMax = noIter;
    }

    /** Metoda rozwiazujaca */
    public void doRun() {
        initBestSolutionLegal();
        adjustNoIterMaxValue();
        mCost = new CostFromArticle(mGraph, mBestSolution);
        mBestCost = mCost.getCurrentCost();
        mCurrentSolution = mBestSolution.clone();
        mNoChangeIter = 0;
        mNoIter = 0;
        long startTime = System.currentTimeMillis();

        while (mNoChangeIter < mNoChangeIterMax) {
            mNoChangeIter++;

            while (mNoIter < mNoIterMax) {
                mNoIter++;
                // probujemy znalezc nowe rozwiazanie
                VertexChange change = generateNewSolutionLegal(mCurrentSolution);
                if (!change.skipMe()) continue;

                int currentCost = mCost.costAfterChange(change);
                mCost.applyChange(change, currentCost);
                mCurrentSolution[change.getVertexId()] = change.getNewColor();

                // Aktualizujemy najlepsze rozwiazanie
                if (currentCost < mBestCost) {
                    mNoChangeIter = 0;
                    mBestCost = currentCost;
                    mBestSolution = mCurrentSolution.clone();
                }
            }
        }

        mComputingTime = System.currentTimeMillis() - startTime;
        mDone = true;
    }

    /** Probuje zmienic 1 kolor w losowym wierzcholku */
    protected VertexChange generateNewSolutionLegal(int[] tab) {
        // Unikamy zapetlenia dalej
        if (mGraph.getVerticesCount() == 0 || mGraph.getEdgesCount() == 0)
            return new VertexChange(0, 0, 0, false);

        int colorToSet = tab[mRandom.nextInt(mGraph.getVerticesCount())];
        int toChangeIndex = mRandom.nextInt(mGraph.getVerticesCount());
        // szukamy miejsca gdzie mozemy zmienic kolor
        while (tab[toChangeIndex] == colorToSet)
            toChangeIndex = mRandom.nextInt(mGraph.getVerticesCount());

        // sprawdzamy czy po zmianie wszystkie sasiednie wierzcholki beda mialy
        // rozne kolory
        boolean valid = true;
        for (Vertex neigh : mGraph.getAdjacent(toChangeIndex)) {
            if (tab[neigh.getId()] == colorToSet) valid = false;
        }

        return new VertexChange(toChangeIndex, tab[toChangeIndex], colorToSet,
                valid);
    }

    @Override
    public String getMethodName() {
        return "Random Search";
    }

    @Override
    public String getMethodParameters() {
        return "mNoChangesMax=" + mNoChangeIterMax + " mNoIterMax="
                + mNoIterMax;
    }

    @Override
    public String getMethodOutcome() {
        return "MinColorCount= " + getMinColorCount();
    }
}
